The invention relates to a system for retrieving blocks of data, such as audio and/or video, from a storage medium and supplying the blocks in the form of a plurality of streams to users, wherein a stream of a first class of the streams may have an actual bit rate between a first minimum bit rate and a first maximum bit rate, the first minimum bit rate and the first maximum bit rate potentially being identical thus yielding a constant bit rate, wherein a stream of a second class of the streams may have an actual bit rate between a second minimum bit rate and a second maximum bit rate, the second minimum bit rate and the second maximum bit rate potentially being identical thus yielding a constant bit rate, and wherein the first maximum bit rate is substantially higher than the second maximum bit rate, the system comprising: for each stream an associated buffer for storing the blocks of data; a reader for in a sweep reading a data block from the storage medium for each stream of a selected group of the streams and for storing the read blocks in the respective buffers; and a scheduler for repeatedly selecting the group of the streams for which a block is to be read in a next sweep of the reader.
The invention further relates to a method of retrieving blocks of data, such as audio and/or video, from a storage medium and supplying the blocks in the form of a plurality of streams to users, wherein a stream of a first class of the streams may have an actual bit rate between a first minimum bit rate and a first maximum bit rate, the first minimum bit rate and the first maximum bit rate potentially being identical thus yielding a constant bit rate, wherein a stream of a second class of the streams may have an actual bit rate between a second minimum bit rate and a second maximum bit rate, the second minimum bit rate and the second maximum bit rate potentially being identical thus yielding a constant bit rate, and wherein the first maximum bit rate is substantially higher than the second maximum bit rate, the method comprising the steps of: for each stream storing the blocks of data in an associated buffer; in a sweep reading a data block from the storage medium for each stream of a selected group of the streams and storing the read blocks in the respective buffers; and repeatedly selecting the group of the streams for which a block is to be read in a next sweep.
Such a system and method are described in the paper xe2x80x9cDisk scheduling for variable-rate data streamsxe2x80x9d, J. Korst, V. Pronk, and P. Coumans, Proceedings European Workshop on Interactive Distributed Multimedia Systems and Telecommunication Services, IDMS ""97, Darmstadt, September 10-12, Lecture Notes in Computer Science, 1309 (1997) 119-132. The known system is a video on demand server, also called multimedia server, which provides a plurality of users with audio and video data, which is stored on the disks of the system. The system repeatedly fetches a block of data for each of the users and stores it in respective buffers, each of which has room for a number of data blocks. The buffers are implemented in relatively fast Random Access Memory. A user consumes data from a corresponding buffer via some communication network at a rate that may vary between zero and a maximum consumption rate. Users may have mutually different maximum consumption rates.
In order to use the disks efficiently, the known system operates in so-called sweeps, also called rounds, whereby blocks are fetched from disk in a single sweeping movement of the disk reading heads. A scheduler determines at the beginning of a sweep which buffers have enough free space for receiving a new block. The scheduler then orders a block of data for these buffers from the disk reader. The size of the buffer of each user is designed in such a way that the buffer does not become empty before actually receiving a new block. The cited paper describes for instance the double buffer algorithm for fixed consumption rates and the triple buffer algorithm for variable consumption rates. In the double buffer algorithm, the buffer can contain two blocks of data and in the triple buffer algorithm, the buffer can contain three blocks of data. A block must contain enough data for a user to consume at a maximum rate during the period of a worst-case sweep. The size of a block of each of the streams must therefore at least be equal to the product of the maximum duration of the sweep and the maximum consumption rate of the respective stream. The duration of a sweep is determined by the actual blocks to be fetched, since each block requires a switch time for locating the block on the disk and a transfer time for actually reading the block from the disk at a given transfer rate. The switch time and the transfer rate are dependent on the specific hard disks used in the system. The transfer time is further dependent on the size of the block to be read, since a larger block will require a longer time to be read. Given the above constraints, the minimum respective block sizes are calculated on the basis of the performance parameters of the hard disks of the system and on the basis of the required maximum number of users to be serviced.
It is an object of the invention to provide a system as described in the preamble in which the total memory required to implement the buffers for the streams is less than in the known system. This object is achieved according to the invention in a system, which is characterized in that the scheduler is operative to select a stream of the second class less often in the group for which a block is to be read than a stream of the first class, such in the situation where the actual bit rate of the stream of the second class equals the second maximum bit rate and the actual bit rate of the stream of the first class equals the first maximum bit rate. So in the steady situation, where both streams are consumed at their respective maximum rates, the stream of the second class, i.e. the one with the smaller consumption rate, is serviced less often. In the context of this description, servicing a stream means that the scheduler verifies whether the buffer of this stream has enough free space to receive a new block and if such is the case, selects this stream into the group for which a block is to be read in the next sweep, and have this block read. As a result of servicing this stream less often, the sweep or sweeps in which the data stream of the second class is not serviced will be shorter. This means that the size of a block for the stream of the first class may be designed smaller because it must contain now at least sufficient data to be consumed during the shorter period of the sweep. The penalty for not servicing the stream of the second class in every sweep is that the size of a block for this stream is to be designed larger, since it must contain enough data to be consumed during a number of sweeps. It can be shown that the decrease of the size of the block for the stream of the first class is larger than the increase of the size of the block for the stream of the second class. Therefore, the sum of the size of the blocks has decreased and the overall memory required for the buffers in the system has decreased. The fact that the sum of the block sizes has decreased is caused by the fact that the consumption rate of the stream of the second class is smaller than the one of the stream of the first class. In the known system, this has the result that the block size for the stream of the second class is relatively small and that the switch time for such a block is relatively large. By servicing the stream of the second class less often, the relative contribution of the switch time becomes smaller and the disk is being used more efficiently.
An embodiment of the system according to the invention is described in claim 2. In the steady situation of this embodiment, a high bit rate stream is serviced every sweep and a low bit rate stream every k sweeps, which provides a simple mechanism to service a low bit rate stream less often than a high bit rate stream. Choosing k in dependence on the respective maximum consumption rates provides a good way of finding a value for k at which the memory required for the buffers is as small as possible.
An embodiment of the system according to the invention is described in claim 3. Servicing all low bit rate streams in one particular sweep, which is subsequently followed by kxe2x88x921 sweeps in which none of the low bit rate streams is being serviced, is a simple mechanism for servicing a low bit rate stream less often then a high bit rate stream.
An embodiment of the system according to the invention is described in claim 4. Evenly distributing the servicing of the low bit rate streams over the sweeps gives a further reduction of the amount of memory required for the buffers. This is because the switching overhead for the low bit rate streams is no longer concentrated in one sweep. This concentration leads to a large sweep requiring a larger buffer to contain the amount of data for the high bit rate streams consumed during this sweep. By spreading the overhead over all sweeps, each sweep is increased slightly but their individual duration is shorter than the duration of the large sweep. This means that the buffers for the high bit rate streams may be chosen smaller.
It is a further object of the invention to provide a method as described in the preamble in which the total memory for buffering the blocks of the streams is less than in the known system. This object is achieved according to the invention in a method, which is characterized in that a stream of the second class is selected less often in the group for which a block is to be read than a stream of the first class, such in the situation where the actual bit rate of the stream of the second class equals the second maximum bit rate and the actual bit rate of the stream of the first class equals the first maximum bit rate.